class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False

class WordDictionary:

    def __init__(self):
        self.root = Node()


    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if not curr.children[ord(c) - ord('a')]:
                curr.children[ord(c) - ord('a')] = Node()
            curr = curr.children[ord(c) - ord('a')]
        curr.is_word = True


    def search(self, word: str) -> bool:

        def dfs(node, word, index):
            if index == len(word):
                return node.is_word;
            c = word[index]
            if c != '.':
                if not node.children[ord(c) - ord('a')]:
                    return False
                return dfs(node.children[ord(c) - ord('a')], word, index + 1)
            else:
                for child in node.children:
                    if child and dfs(child, word, index + 1):
                        return True
                return False

        return dfs(self.root, word, 0)



# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)